package likou;

import java.util.Arrays;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/08/08 11:07
 */
public class _5841 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(longestObstacleCourseAtEachPosition(new int[]{1, 6, 8, 10, 10, 2, 8, 3, 3, 6, 4, 3, 3, 4, 6, 2, 3, 10, 2, 5})));
    }

    public static int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int[] res = new int[obstacles.length];
        int[] maxRes = new int[obstacles.length];
        maxRes[0] = 0;
        for (int i = 0; i < obstacles.length; i++) {
            int max = 1;
            int j = i - 1;
            //找到第一个
            for (; j >= 0; j--) {
                if (max > j) break;
                if (obstacles[j] <= obstacles[i]) {
                    max = Math.max(res[j] + 1, max);
                    break;
                }
            }
            //往前面继续找，只找更大的
            while (maxRes[j]!=j){
                j = maxRes[j];
            }


            if (i > 0) {
                if (max >= res[i - 1]) {
                    maxRes[i] = i - 1;
                } else if (max >= res[maxRes[i - 1]]) {
                    maxRes[i] = i;
                } else {
                    maxRes[i] = i - 1;
                }
            }
            res[i] = max;
        }
        return res;
    }
}
